/*---------------------------------------------------------------------------*\
|* This file is part of the koala project with MIT License.                  *|
|* Copyright (c) James <zhuguangxiang@gmail.com>                             *|
\*--------------------------------------------------------------------------**/

#include "ir.h"
#include "util/log.h"

#ifdef __cplusplus
extern "C" {
#endif

/**
 * "Engineering a Compiler"
 * "A Simple, Fast Dominance Algorithm"
 */

#define PRE_ORDER  1
#define POST_ORDER 2

typedef struct _KlrSSAContext {
    KlrFunc *func;
    int order;
    /* reverse visit vector is the REVERSE POST ORDER */
    Vector vec;
    int count;
    int *idom;
    int (*intersect)(int b1, int b2, struct _KlrSSAContext *ctx);
} KlrSSAContext;

static int pre_order_intersect(int b1, int b2, struct _KlrSSAContext *ctx)
{
    while (b1 != b2) {
        while (b1 < b2) {
            b2 = ctx->idom[b2];
        }
        while (b1 > b2) {
            b1 = ctx->idom[b1];
        }
    }
    return b1;
}

static int post_order_intersect(int b1, int b2, struct _KlrSSAContext *ctx)
{
    while (b1 != b2) {
        while (b1 < b2) {
            expect(b1 >= 0 && b1 < ctx->count);
            b1 = ctx->idom[b1];
        }
        while (b1 > b2) {
            expect(b2 >= 0 && b2 < ctx->count);
            b2 = ctx->idom[b2];
        }
    }
    return b1;
}

static void dfs(KlrBasicBlock *bb, Vector *post_order, KlrFunc *func)
{
    if (bb->visited) return;
    bb->visited = 1;

    KlrEdge *edge;
    edge_out_foreach(edge, bb, { dfs(edge->dst, post_order, func); });
    if (bb != func->sbb && bb != func->ebb) vector_push_back(post_order, &bb);
}

static void clear_bb_visited(KlrFunc *func)
{
    KlrBasicBlock *bb;
    basic_block_foreach(bb, func, { bb->visited = 0; });
}

static void klr_build_topo_order(KlrFunc *func)
{
    printf("reverse post order:\n\n");

    clear_bb_visited(func);

    Vector post_order;
    vector_init_ptr(&post_order);

    dfs(func->sbb, &post_order, func);
    KlrBasicBlock **item;
    vector_foreach_reverse(item, &post_order, {
        if ((*item)->name[0])
            printf("%%%s ", (*item)->name);
        else
            printf("%%%d ", (*item)->tag);
    });
    printf("\n\n");
}

void klr_gen_ssa_form(KlrFunc *func) { klr_build_topo_order(func); }

#ifdef __cplusplus
}
#endif
